import numpy as np


class Graph:

    def __init__(self, adj_matrix):
        # 1. 初始化图基本信息
        self.vertex_num = adj_matrix.shape[0]
        self.adj_matrix = adj_matrix
        # 2. 初始化任意两点间最短路径为直接路径，即不经过任何中间点的路径
        self.path_matrix = np.zeros((self.vertex_num, self.vertex_num))
        for i in range(self.vertex_num):
            self.path_matrix[i] = i
        # 3. 计算任意两点间最短距离
        self.floyd()

    def __str__(self):
        return str(self.adj_matrix)

    def floyd(self):
        for k in range(1, self.vertex_num):
            for i in range(1, self.vertex_num):
                for j in range(1, self.vertex_num):
                    if self.adj_matrix[i][k] + self.adj_matrix[k][j] < self.adj_matrix[i][j]:
                        self.adj_matrix[i][j] = self.adj_matrix[i][k] + self.adj_matrix[k][j]
                        self.path_matrix[i][j] = self.path_matrix[i][k]

    def print_path(self, i, j):
        k = self.path_matrix[i][j]
        while k != j:
            print(f" ——> {k}")
            k = self.path_matrix[k][j]
        print(f" ——> {j}")

    # @classmethod
    # def from_parts(cls, parts, normalization=False):
    #     parts_num = len(parts)
    #     adj_matrix = np.zeros((parts_num, parts_num))
    #     for i in range(parts_num):
    #         for j in range(parts_num):
    #             if i != j:
    #                 adj_matrix[i][j] = parts[i].calc_distance(parts[j])
    #     adj_matrix = (np.round(adj_matrix / np.mean(adj_matrix), decimals=2)) \
    #         if normalization else np.round(adj_matrix, decimals=2)
    #     return Graph(adj_matrix)
